The identification of the position of a device when outdoors, for example to identify the position of a mobile phone, is primarily done using GPS (Global Positioning System). However, GPS data is not always available, particularly when a device is indoors, due to its reliance on radio signals emitted by dedicated GPS satellites. As a result, various positioning systems have been proposed that use do not use GPS data, but rather use motion measurements provided by inertial measuring units of devices, such as accelerometer, magnetometer and gyroscopic units. However, all systems so far proposed have drawbacks, and none has become predominant.
Electronic maps showing the boundaries in an area are becoming increasingly available, particularly for indoor areas. Such an electronic map can be considered to be a spatial graph with constraints. The most basic electronic map corresponds to a floor plan, which identifies the constraints on the possible motion within the floor plan, in other words the walls through which a person is not able to walk. Maps may also include other useful data (essentially metadata), such as the location of WiFi access points, radio fingerprints, signal strength peaks or distorted geomagnetic fields.
Various map matching techniques have been suggested for use with indoor positioning systems. In map matching, a series of observations are obtained over time, such as inertial trajectories or RF scans. Map matching then involves attempting to reconcile the observations with the constraints provided by the map, in order to estimate the most feasible trajectory (i.e. sequence of positions of the device), in other words the trajectory that violates the fewest constraints.
Suggested map matching techniques include those based on recursive Bayesian filters, such as particle/Kalman filters and Hidden Markov Models (HMMs). However, these techniques are computationally expensive, and so are typically run remotely on a server contacted via the Internet, rather than on a device itself. This leads to time delays (“lag”), lack of service in the absence of an reliable Internet connection, and the potential leaking of sensitive sensor/location information to third parties. These techniques also typically require high-precision sensor data in order to provide accurate results, leading to power drain on the device.
The present invention seeks to solve and/or mitigate the above-mentioned problems. Alternatively and/or additionally, the present invention seeks to provide improved positioning systems that are easily extendable to incorporate new types of sensor data in order to provide more accurate results.